package com.lw.leetcode.dp.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * c
 * dp
 * 741. 摘樱桃
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/20 16:46
 */
public class CherryPickup {

    public static void main(String[] args) {
        CherryPickup test = new CherryPickup();

        // 5
//        int[][] arr = {
//                {0, 1, -1},
//                {1, 0, -1},
//                {1, 1, 1}};

        // -1
        int[][] arr = {
                {0, 1, -1},
                {1, -1, -1},
                {1, -1, 1}};

        // 15
//        int[][] arr = {
//                {1, 1, 1, 1, 0, 0, 0},
//                {0, 0, 0, 1, 0, 0, 0},
//                {0, 0, 0, 1, 0, 0, 1},
//                {1, 0, 0, 1, 0, 0, 0},
//                {0, 0, 0, 1, 0, 0, 0},
//                {0, 0, 0, 1, 0, 0, 0},
//                {0, 0, 0, 1, 1, 1, 1}};

        // 15
//        int[][] arr = {
//                {1, 1, -1, 1, 0, 0, 0},
//                {0, 0, -1, 1, 0, 0, 0},
//                {-1, -1, -1, 1, 0, 0, 1},
//                {1, 0, 0, 1, 0, 0, 0},
//                {0, 0, 0, 1, 0, 0, 0},
//                {0, 0, 0, 1, 0, 0, 0},
//                {0, 0, 0, 1, 1, 1, 1}};

        //
//        int[][] arr = Utils.getArr(50,50,-2,2);

        int i = test.cherryPickup(arr);
        System.out.println(i);

    }

    public int cherryPickup(int[][] grid) {
        int m = grid.length;
        int n = m + m - 1;
        int[][][] arr = new int[n][m + 1][m + 1];

        for (int j = 1; j < n; j++) {
            int[][] ints = arr[j];
            for (int i = 0; i <= m; i++) {
                ints[i][0] = -1;
                ints[0][i] = -1;
            }
        }
        for (int[] ints : arr[0]) {
            Arrays.fill(ints, -1);
        }
        arr[0][1][1] = grid[0][0];
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= m; j++) {
                int a1 = j - 1;
                int b1 = i - a1;
                for (int k = 1; k <= m; k++) {
                    int a2 = k - 1;
                    int b2 = i - a2;
                    if (b1 < 0 || b1 >= m || b2 < 0 || b2 >= m || grid[a1][b1] == -1 || grid[a2][b2] == -1) {
                        arr[i][j][k] = -1;
                        continue;
                    }
                    int t = Math.max(Math.max(arr[i - 1][j][k], arr[i - 1][j - 1][k]), Math.max(arr[i - 1][j][k - 1], arr[i - 1][j - 1][k - 1]));
                    if (t == -1) {
                        arr[i][j][k] = -1;
                        continue;
                    }
                    arr[i][j][k] = t + (j == k ? grid[a1][b1] : grid[a1][b1] + grid[a2][b2]);
                }
            }
        }
        int[][] ints = arr[n - 1];
        int max = 0;
        for (int[] anInt : ints) {
            for (int i : anInt) {
                max = Math.max(max, i);
            }
        }
        return max;
    }

}
